import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 98152
 * Date: 2024-12-11
 * Time: 17:00
 */
public class Solution3 {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int max = nums[n-1];
        int[] arr = new int[max+1];
        for(int i = 0; i < n; i++) {
            arr[nums[i]] += nums[i];
        }

        int[] f = new int[max+1];
        int[] g = new int[max+1];
        f[0] = arr[0];
        for(int i = 1; i < max+1; i++) {
            f[i] = g[i-1] + arr[i];
            g[i] = Math.max(f[i-1], g[i-1]);
        }
        return Math.max(f[max], g[max]);
    }
}
